문제 소개

문제 링크 : https://boj.kr/31577

Tier : Gold III

Tag : Math, Constructive

컴퓨터가 총 15개 존재하며, 각 컴퓨터에는 서로 다른 파일을 최대 8개까지 저장할 수 있다.

이때, 이 중 5개의 컴퓨터가 손상되어도 나머지 컴퓨터를 통해 총 20가지의 파일을 복구할 수 있어야 한다.

파일은 1부터 20까지 번호가 매겨져 있으며, (위의 조건을 충족하도록) 15개의 컴퓨터에 저장할 파일을 8개씩 출력해야 한다.

풀이

1. 손상될 컴퓨터의 대상이 무작위라는 점에 대해 생각해보기

특정 컴퓨터가 손상된 경우 해당 컴퓨터에 존재하는 파일은 사용할 수 없게 된다.

이때 우리는 손상된 컴퓨터가 무작위라는 점에 주목해야 한다.

즉, 특정되지 않으므로 어떤 상황에서도 파일이 보존되는 조건을 생각해봐야 한다.

2. 특정 파일이 항상 보존되는 조건 찾기

특정 파일은 동일한 컴퓨터에 중복하여 넣을 수 없으므로, 1 ~ 15번째 컴퓨터에 최대 하나씩 넣을 수 있다.

이때, 최소 6개의 컴퓨터에 동일한 파일을 넣을 경우 어떠한 상황에서도 보존됨을 알 수 있다.

왜냐하면, 손상되는 컴퓨터는 5개이기 때문에 최소 한 컴퓨터에는 파일이 보존된다.

3. 컴퓨터에 저장할 파일 구성하기

즉, 우리는 20개의 파일을 모두 보존하기 위해 최소 20 * 6 = 120개의 파일을 저장할 공간을 확보해야 한다.

문제 조건에서는 (15개의 컴퓨터) * (8개의 파일) = 120이므로 정확히 맞아떨어진다.

따라서, 파일 1 ~ 20 각각 6개씩 15개의 컴퓨터에 적절히 배치하면 된다.

다양한 방법이 있지만, 필자는 다음과 같이 구성하였다.

• 111111 222222 333333 ... 와 같이 파일을 일렬로 배치한다.

• 위와 같이 배치하면 각 파일의 인덱스는 0 ~ 119가 되는데, (인덱스를 15로 나눈 나머지) 번째 컴퓨터에 해당 파일을 배치한다.

• 컴퓨터는 총 15개이고, 특정 파일은 6개이므로 동일한 파일이 동일한 컴퓨터에 두 개 이상 배치되는 경우는 없다. 따라서 위의 조건을 모두 충족한다.

코드

1import sys
2input = lambda: sys.stdin.readline().rstrip()
3
4if __name__ == "__main__":
5	sequences = [[] for _ in range(15)]
6
7	for x in range(120):
8		sequences[x % 15].append((x // 6) + 1)
9
10	for sequence in sequences:
11		print(*sequence)

1import sys
2input = lambda: sys.stdin.readline().rstrip()
3
4if __name__ == "__main__":
5	sequences = [[] for _ in range(15)]
6
7	for x in range(120):
8		sequences[x % 15].append((x // 6) + 1)
9
10	for sequence in sequences:
11		print(*sequence)